Permutation in string

Time: O(N); Space: O(1); medium

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1.

In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input: s1 = “ab”, s2 = “eidbaooo”

Output: True

Explanation:

  • s2 contains one permutation of s1 (“ba”).

Example 2:

Input: s1= “ab”, s2 = “eidboaoo”

Output: False

Constraints:

  • The input strings only contain lower case letters.

  • The length of both given strings is in range [1, 10,000].

Hints:

  1. Obviously, brute force will result in TLE. Think of something else.

  2. How will you check whether one string is a permutation of another string?

  3. One way is to sort the string and then compare. But, Is there a better way?

  4. If one string is a permutation of another string then they must one common metric. What is that?

  5. Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies?

  6. What about hash table? An array of size 26?

1. Using counts

[3]:

import collections

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        counts = collections.Counter(s1)
        l = len(s1)

        for i in range(len(s2)):
            if counts[s2[i]] > 0:
                l -= 1
            counts[s2[i]] -= 1
            if l == 0:
                return True

            start = i + 1 - len(s1)
            if start >= 0:
                counts[s2[start]] += 1
                if counts[s2[start]] > 0:
                    l += 1

        return False

[4]:

s = Solution1()

s1 = "ab"
s2 = "eidbaooo"
assert s.checkInclusion(s1, s2) == True

s1= "ab"
s2 = "eidboaoo"
assert s.checkInclusion(s1, s2) == False

2. Brute Force [O(N!), O(N^2)]

Algorithm

The simplest method is to generate all the permutations of the short string and to check if the generated permutation is a substring of the longer string.

In order to generate all the possible pairings, we make use of a function permute(string_1, string_2, current_index). This function creates all the possible permutations of the short string s1s1.

To do so, permute takes the index of the current element current_index as one of the arguments. Then, it swaps the current element with every other element in the array, lying towards its right, so as to generate a new ordering of the array elements. After the swapping has been done, it makes another call to permute but this time with the index of the next element in the array. While returning back, we reverse the swapping done in the current function call.

Thus, when we reach the end of the array, a new ordering of the array’s elements is generated. The following animation depicts the process of generating the permutations.

See details: https://leetcode.com/problems/permutation-in-string

3. Using sorting [O(L1xLog(L1))+(L2-L1)xL1xLog(L1)), O(L1)

Algorithm

The idea behind this approach is that one string will be a permutation of another string only if both of them contain the same characters the same number of times. One string x is a permutation of other string y only if sorted(x)=sorted(y).

In order to check this, we can sort the two strings and compare them. We sort the short string s1 and all the substrings of s2, sort them and compare them with the sorted s1 string. If the two match completely, s1’s permutation is a substring of s2, otherwise not.

See details: https://leetcode.com/problems/permutation-in-string

4. Using Hashmap [O(L1+26xL1x(L2-L1)), O(1)]

Algorithm

As discussed above, one string will be a permutation of another string only if both of them contain the same charaters with the same frequency. We can consider every possible substring in the long string s2 of the same length as that of s1 and check the frequency of occurence of the characters appearing in the two. If the frequencies of every letter match exactly, then only s1s1’s permutation can be a substring of s2.

In order to implement this approach, instead of sorting and then comparing the elements for equality, we make use of a hashmap s1maps1map which stores the frequency of occurence of all the characters in the short string s1. We consider every possible substring of s2 of the same length as that of s1s1, find its corresponding hashmap as well, namely s2map. Thus, the substrings considered can be viewed as a window of length as that of s1s1 iterating over s2. If the two hashmaps obtained are identical for any such window, we can conclude that s1’s permutation is a substring of s2, otherwise not.

See details: https://leetcode.com/problems/permutation-in-string

5. Using Array [O(L1+26xL1x(L2-L1)), O(1)]

Algorithm

Instead of making use of a special HashMap datastructure just to store the frequency of occurence of characters, we can use a simpler array data structure to store the frequencies.

Given strings contains only lowercase alphabets (‘a’ to ‘z’).

So we need to take an array of size 26.The rest of the process remains the same as the last approach.

See details: https://leetcode.com/problems/permutation-in-string

6. Sliding Window [O(L1+26xL1x(L2-L1)), O(1)]

Algorithm

Instead of generating the hashmap afresh for every window considered in s2, we can create the hashmap just once for the first window in s2.

Then, later on when we slide the window, we know that we add one preceding character and add a new succeeding character to the new window considered.

Thus, we can update the hashmap by just updating the indices associated with those two characters only.

Again, for every updated hashmap, we compare all the elements of the hashmap for equality to get the required result.

See details: https://leetcode.com/problems/permutation-in-string

7. Optimized Sliding Window [O(L1 + (L2-L1), O(1)

Algorithm

The last approach can be optimized, if instead of comparing all the elements of the hashmaps for every updated s2maps2map corresponding to every window of s2 considered, we keep a track of the number of elements which were already matching in the earlier hashmap and update just the count of matching elements when we shift the window towards the right.

To do so, we maintain a countcount variable, which stores the number of characters(out of the 26 alphabets), which have the same frequency of occurence in s1 and the current window in s2.

When we slide the window: * if the deduction of the last element and the addition of the new element leads to a new frequency match of any of the characters, we increment the countcount by 1. * If not, we keep the countcount intact. But, if a character whose frequency was the same earlier(prior to addition and removal) is added, it now leads to a frequency mismatch which is taken into account by decrementing the same countcount variable.

If, after the shifting of the window, the countcount evaluates to 26, it means all the characters match in frequency totally. So, we return a True in that case immediately.

See details: https://leetcode.com/problems/permutation-in-string